package algorithm_demo.demo_advanced;

import java.util.HashMap;
import java.util.Map;

/**
 * arr数组，有正数，负数，0， 在arr数组中符合sum == k的最长子数组的长度是多少
 *
 * @author Api
 * @date 2023/4/3 0:32
 */
public class Code16_LongestSumSubArrayLength {
    public static int maxLength(int[] arr, int k){
        if (arr == null || arr.length == 0){
            return 0;
        }
        // key:前缀和
        // value : 0~value这个前缀和是最早出现key这个值的
        Map<Integer, Integer> map = new HashMap<>();
        map.put(0,-1);//重要 0这个累加和，出现在下标为-1的位置
        int len = 0;
        int sum = 0;
        for(int i = 0; i< arr.length; i++){
            sum+=arr[i];
            if (map.containsKey(sum-k)){
                len = Math.max(i-map.get(sum-k), len);
            }
            if (!map.containsKey(sum)){
                map.put(sum, i);
            }
        }
        return len;
    }
}
